题解 AT5659@洛谷 | 5659@Atcoder 【[AGC040A] ><】

~~看一下这道题的题面，决定放弃这道题，~~突然想起在 $\text{Atcoder}$ 上可能会有英文翻译，便到原题看了一眼，真的有。题意大概是：

• 输入一个仅由 $\lt$ 和 $\gt$ 组成的字符串 $s$ ，假设共 $l$ 位；
• 请你构造一个共 $l+1$ 位数列 $a$ ，满足 $\sum a_i$ 最小，同时 $a_i$ 与 $a_{i+1}$ 的关系是 $s_i$ 中的字符（即：大于或小于）。
• 输出 $\sum a_i$

看了一眼数据规模，想到一个 $O(n)$ 的暴力解法：

• 从前往后扫一遍字符串，构造 $s_i='\lt'$ 对应的值，具体方法： $a_{i+1}=a_i+1$ ，可以证明这是最优方案；
• 从后往前扫一遍字符串，构造 $s_i='\gt'$ 对应的值，具体方法： $a_i=\max(a_i, a_{i+1}+1)$ ，可以证明这是最优方案。

最后再扫一遍记好的数组，记录 $ans=\sum a_i$ ，输出即可，注意 $ans$ 可能需要使用 $\text{long long}$。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s;
ll l, a[500001];
ll ans; 

int main()
{
	cin>>s;
	s = " " + s;
	l = s.length() - 1;
	for(int i=1;i<=l;i++) (s[i] == '<') ? (a[i+1] = a[i] + 1) : (a[i+1]);
	for(int i=l;i>=1;i--) (s[i] == '>') ? (a[i] = max(a[i], a[i+1]+1)) : (a[i]);
	for(int i=1;i<=l+1;i++) ans += a[i];
	cout<<ans<<endl;
	return 0;
}